home *** CD-ROM | disk | FTP | other *** search
/ Acorn RISC PD-CD 1 / Acorn RISC PD-CD 1.iso / games / _kalaha / source / c / think < prev   
Encoding:
Text File  |  1992-03-04  |  9.3 KB  |  417 lines

  1.  
  2. /* routines to find best moves */
  3.  
  4.  
  5.                            /* General */
  6.  
  7. /*  At first sight it seems easy to look ahead a long way: there
  8. are only 6 choices for each move and 6^6 (say) is not too big.
  9. My first attempt looked ahead like this regardlesss of whose
  10. moves they were, then gave an extra score at the final
  11. evaluation according to who had the next move.  It didn't play
  12. well.  The whose-go score was too crude, and it was unaware of
  13. promising situations building up on your side: you might have
  14. ten goes in a row a few moves hence and it would know little of
  15. it. */ 
  16.  
  17. /* So then I tried trying all move sequences ending in loss of
  18. control as a single move, and then looked ahead 3 or 4 moves.
  19. It was harder to beat but still not much good unless allowed 10
  20. minutes per move to think.  A little late in  the day I
  21. calculated how many move sequences there might be.  If your
  22. ball-counts are 6 4 2 3 2 1 you have 321 choices of
  23. move-sequences before lsoing control, and 100 choices happen in
  24. typical games. */
  25.  
  26. /* So the current (20.5.91) method is to find the best N
  27. move-sequences (ie the best looking 1 turn ahead); then for each
  28. of those look further ahead.  At the hardest level it examines
  29. the results of (up to) 14 "best" moves, 9 replies, 6 moves, 3
  30. replies, 2 moves, 1 "reasonable" reply.  Then it does (the first
  31. part of) the best of the 14, and if still it's go, repeats.  It
  32. seems to play a pretty mean game */
  33.  
  34. /* 14.12.91:  It was possible to beat this by learning how it
  35. played.  Despite some randomness, it almost always made the same
  36. mistakes.  I tries various alteranatives to the 14,9,6,3,2,1
  37. scheme.  These worked for a while but I soon picked up different
  38. mistakes (unless it was allowed a long time to think).  The
  39. prehosnt solution to this is to randomise the sequence itself. 
  40. This produces some real variation in its play and I haven't
  41. beaten it at the hardest level for a quite a while */
  42.  
  43.  
  44. #include "kalaha.h"
  45.    
  46.  
  47.  
  48.                                        
  49.  
  50.  
  51.  
  52.  
  53. /************* STATIC ****************************/
  54.  
  55. /* these are for looking ahead one complete turn or go.  After
  56. calling find_next_go(), moves[] will contain a sequence of 0-5's
  57. ending in loss of control.  go_results[] contains the initial
  58. intermediate and final effects of this sequence. nofmoves is
  59. length of sequence, and complete indicates whether or not it
  60. does end in loss of control (within find_next_go()). */
  61.  
  62. /* they are initiallised with go_results[0] containing current
  63. game, nofmoves = 0, complete = FALSE. */
  64.  
  65. static char go_results[MAX_MOVES][14];
  66. static char moves[MAX_MOVES];
  67. static int nofmoves;
  68. static BOOL complete;
  69.  
  70.  
  71.  
  72. /************* FUNCTIONS ********************/
  73.  
  74. int stupid_move(char * here);
  75.  
  76. MoveScore best_n_move(int depth, char *here);
  77.  
  78. static int virtual_move(char * h, char * prev, int p);
  79.  
  80. static BOOL find_next_go(void);
  81.  
  82. static void init_go_arrays(char *here);
  83.  
  84. static int find_best_goes(int n, char *here, char best[MAXBESTGOES][15]);
  85.  
  86. static int best_1_score(char *here);
  87.  
  88.  
  89.  
  90. int stupid_move(char * here)
  91. {
  92. int i, score, move, state;
  93. char next[14];
  94.  
  95. score = here[6] - here[13];
  96. move = 0;
  97. for (i=0; i<6; i++)  
  98.   {
  99.   int randbit, s;
  100.   if (here[i] == 0) continue;  
  101.   randbit = rand() & 1;
  102.   state = virtual_move(next, here, i);
  103.   s = next[6] - next[13];
  104.   if (state == MY)
  105.     s += 2;
  106.   if (s+randbit > score)
  107.     {
  108.     score = s;
  109.     move = i;
  110.     }
  111.   }
  112. return move;
  113. }
  114.  
  115.  
  116. static int cons[] = {1,2,3,6,9,14};
  117.  
  118. void setup_cons_arr(void)
  119. {
  120.  
  121. if (level < 3)
  122.   {
  123.   cons[0] = 1; 
  124.   cons[1] = 2; 
  125.   cons[2] = 2 + rand()%4; 
  126.   cons[3] = 4 + rand()%8;
  127.   return;
  128.   }
  129. cons[5] = 8 + rand()%12;
  130. cons[4] = 120/cons[4];
  131. cons[3] = 4 + rand()%5;
  132. cons[2] = 21/cons[3];
  133. cons[1] = 2;
  134. cons[0] = 1;
  135. }
  136.  
  137.  
  138.  
  139. MoveScore best_n_move(int depth, char *here)
  140. {
  141. MoveScore temp;
  142. int num, i, s, consider, randomnumber;
  143. char next[14];
  144. char best[MAXBESTGOES][15];
  145.  
  146.  
  147.  
  148. if (depth<1) 
  149.   {
  150.   temp.move = 0; /* irrelavant, stops compiler warning */
  151.   temp.score = best_1_score(here);
  152.   return temp;
  153.   }
  154.  
  155. /* deal with game over seperately.  Its faster, but more important
  156.  find_next_go() makes NO SENSE if no possible moves */
  157. if (here[0]==0 && here[1]==0 && here[2]==0 && here[3]==0 && here[4]==0 && here[5]==0 )
  158.   {
  159.   temp.move = 0; /* irrelevant */ 
  160.   temp.score = here[6] - here[13];
  161.   return temp;
  162.   }            
  163.  
  164. setup_cons_arr();
  165. randomnumber = rand();
  166.  
  167. consider = cons[depth];
  168. wassert(consider<MAXBESTGOES);
  169. num = find_best_goes(consider , here, best);
  170. wassert(num < 32);
  171. temp.score = -99999;
  172. for (i=0; i<num; i++)
  173.   {
  174.   int j, randbit;
  175.   for (j=0; j<14; j++)
  176.     {    
  177.     if (j<7)
  178.       next[j] = best[i][j+7];
  179.     else
  180.       next[j] = best[i][j-7];
  181.     }
  182.   randbit = (randomnumber >> i) & 1;
  183.   s = - best_n_move(depth-1, next).score;
  184.   if (s+randbit > temp.score)
  185.     {
  186.     temp.score = s;
  187.     temp.move = best[i][14];
  188.     }
  189.   }
  190. return temp;
  191. }
  192.  
  193.  
  194.  
  195. static int best_1_score(char *here)
  196. {
  197. char next[14];
  198. int i, state, score, j;
  199.  
  200. /* find the "last" move that gives an extra go or get j = -1 if
  201. none */ 
  202. for (j=5; j>=0; j--)
  203.   {
  204.   int t;
  205.   t = here[j] + j;
  206.   if (t==6 || t==19 || t==32 || t== 45)
  207.      break;
  208.   }
  209. /* If one exists, this move is done, and function called
  210. recursively.  I think this is a reasonable strategy for weeding
  211. out a lot of moves if there are a lot.  Eg 
  212.                   8 0 0 0 0 0
  213.  
  214.                   6 4 2 3 2 1 
  215. has 321 possible move sequences.  This strategy finds 28 
  216. including 1st and 4th.  
  217.  */
  218.  
  219.  
  220. score = here[6] - here[13];
  221. /* NB score cannot get worse so this is default 
  222. in case game over, lower bound otherwise */
  223.  
  224. for (i=0; i<6; i++)
  225.   {
  226.   int s;
  227.   if (here[i] == 0) continue;  
  228.   state = virtual_move(next, here, i);
  229.   if (state == MY  &&  i != j)     /* ignore other extra goes */
  230.     continue;
  231.   if (i==j)                        /* do this one */
  232.     s = best_1_score(next);
  233.   else
  234.     s = next[6] - next[13];
  235.   if (s > score)
  236.     score = s;
  237.   }
  238. return score;
  239. }
  240.  
  241.  
  242.  
  243. static int find_best_goes(int n, char *here, char best[MAXBESTGOES][15] )
  244. {
  245. /* make a list in best[] of the n best complete sequnces of moves, or less
  246. if fewer than n goes.  best[i][0-13] contains resulting game positions,
  247. best[i][14] the first move in sequence.*/
  248.  
  249.  
  250. int score[MAXBESTGOES];
  251. int go, nthworst, worstscore, i, s;
  252.  
  253. init_go_arrays(here);
  254.  
  255. go = 0;
  256. while ( find_next_go() )
  257.   {
  258.   if ( go < n )
  259.     {
  260.     score[go] = go_results[nofmoves][6] - go_results[nofmoves][13];
  261.     memcpy( best[go], go_results[nofmoves], 14);
  262.     best[go][14] = moves[0];
  263.     go++;
  264.     }
  265.   else
  266.     { 
  267.     nthworst = 0;
  268.     worstscore = score[nthworst];
  269.     for (i=1; i<n; i++)
  270.         {
  271.         if (score[i] < worstscore)
  272.             { nthworst = i;  worstscore = score[nthworst]; }
  273.         }
  274.     s = go_results[nofmoves][6] - go_results[nofmoves][13];
  275.     if (s > worstscore)
  276.         {
  277.         memcpy( best[nthworst], go_results[nofmoves], 14);
  278.         best[nthworst][14] = moves[0];
  279.         score[nthworst] = s;
  280.         }
  281.     }
  282.   }
  283. return go;
  284. }
  285.  
  286.  
  287.  
  288.  
  289. static void init_go_arrays(char *here)
  290. {
  291. int i;
  292.  
  293. nofmoves = 0;
  294. complete = FALSE;
  295. for (i=0; i<14; i++)
  296.   go_results[0][i] = here[i];
  297. }
  298.   
  299.  
  300.  
  301.  
  302. static BOOL find_next_go(void)
  303. {
  304. int i, state;
  305.  
  306. if (complete)
  307.   {
  308.   do                                    /* backtrack */
  309.     {
  310.     nofmoves--;
  311.     if (nofmoves < 0) return FALSE;    /* backtracked off beginning */
  312.     i = moves[nofmoves] + 1;
  313.     while (i < 6  &&  go_results[nofmoves][i] == 0)
  314.         i++;
  315.     }
  316.   while (i >= 6);
  317.   /* backtracked to a point where there's a replacement move */
  318.  
  319.   moves[nofmoves] = i;
  320.   nofmoves++;
  321.   state = virtual_move( go_results[nofmoves], go_results[nofmoves-1], i);
  322.   if (state == MY)
  323.     complete = FALSE;
  324.   }
  325.  
  326. while (!complete)                 
  327.   {                               /* fill up */
  328.   i = 0;
  329.   while (go_results[nofmoves][i] == 0)  
  330.     i++;
  331.   wassert(i < 6);
  332.   moves[nofmoves] = i;
  333.   nofmoves ++;
  334.   state = virtual_move( go_results[nofmoves], go_results[nofmoves-1], i);
  335.   if (state != MY) 
  336.     complete = TRUE;
  337.   }
  338.  
  339. return TRUE;
  340. }
  341.  
  342.  
  343.  
  344.  
  345. int virtual_move(char * h, char * prev, int p)
  346. /* 
  347. passed game situation in prev[0...13].  posn p, 0<=p<5, is
  348. to move.
  349.              12 11 10  9  8  7
  350.           13                   6
  351.               0  1  2  3  4  5
  352.  
  353. If botgo, this maps directly to screen positions, else add 7 mod 14.
  354. */
  355. /*
  356. Returns: MY,YOUR,OVER according to another go, opp's go, game end
  357.          Updates h[] to new values
  358. */
  359. {
  360. int carry, i, temp;
  361.  
  362. /* virtual move is called ~30K times per move with depth 5,
  363. consider = 14,9,6,3,2.  Following saves >10% compared to memcpy() 
  364. on time to choose move, and allows h==prev */
  365. h[0] = prev[0];   h[1] = prev[1]; h[2] = prev[2];   h[3] = prev[3]; 
  366. h[4] = prev[4];   h[5] = prev[5]; h[6] = prev[6];   h[7] = prev[7]; 
  367. h[8] = prev[8];   h[9] = prev[9]; h[10] = prev[10]; h[11] = prev[11]; 
  368. h[12] = prev[12]; h[13] = prev[13]; 
  369.  
  370. carry = h[p];
  371. h[p] = 0; /*disp*/
  372.  
  373. while (carry-->0)
  374.   {
  375.   p++;
  376.   if (p==13) p=0;
  377.   h[p] += 1; /*disp*/
  378.   }
  379. if (p < 6  &&  h[p] == 1)
  380.   {
  381.   h[p] = 0; /*disp*/
  382.   h[6] += 1; /*disp*/
  383.   temp = h[12-p];
  384.   h[12-p] = 0;  /*disp*/
  385.   h[6] += temp; /*disp*/
  386.   }
  387. if (h[0]==0 && h[1]==0 && h[2]==0 && h[3]==0 && h[4]==0 && h[5]==0)
  388.   {
  389.   for (i=7; i<13; i++)
  390.       {
  391.       temp = h[i];
  392.       h[i] = 0; /*disp*/
  393.       h[6] += temp; /*disp*/
  394.       }
  395.   return OVER;
  396.   }
  397. else if (h[7]==0 && h[8]==0 && h[9]==0 && h[10]==0 && h[11]==0 && h[12]==0)
  398.   {
  399.   for (i=0; i<6; i++)
  400.       {
  401.       temp = h[i];
  402.       h[i] = 0; /*disp*/
  403.       h[6] += temp; /*disp*/
  404.       }
  405.   return OVER;
  406.   }
  407. else
  408.   {
  409.   if (p==6)
  410.       return MY;
  411.   else
  412.       return YOUR;
  413.   }
  414. }
  415.  
  416.  
  417.